package algorithm.leetcode.I401to600;

import java.util.Arrays;
import java.util.Comparator;

/**
 * 有点像 Q56 区间合并
 * 贪心法
 */

public class Q452 {

    public int findMinArrowShots(int[][] points) {
        Arrays.sort(points, (Comparator.comparingInt(o -> o[0])));
        int index = -1;

        for (int i = 0; i < points.length; i++) {
            if (index == -1 || points[index][1] < points[i][0]) {
                points[++index] = points[i];
            }
            else {
                // 和Q56不同的地方在于这里是求区间的交集
                points[index][0] = Math.max(points[index][0], points[i][0]);
                points[index][1] = Math.min(points[index][1], points[i][1]);
            }
        }
        return index+1;
    }

    public static void main(String[] args) {
        Q452 q452 = new Q452();
        int[][] points = new int[4][2];
        points[0] = new int[]{10, 16};
        points[1] = new int[]{2, 8};
        points[2] = new int[]{1, 6};
        points[3] = new int[]{7, 12};
        System.out.println(q452.findMinArrowShots(points));
    }
}
